#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;
const int MAX = 10000;
struct node
{
    int key;
    int next;
} list[MAXN];
bool isexist[MAX] = {false};
int main()
{
    int first, N;
    scanf("%d%d", &first, &N);
    int i;
    int addr;
    for (i = 0; i < N; ++i)
    {
        scanf("%d", &addr);
        scanf("%d%d", &list[addr].key, &list[addr].next);
    }
    int pre = first;
    int pre_removed;
    isexist[abs(list[first].key)] = true;
    int count = 0; //统计删除的结点个数
    int tmnod = list[first].next;
    int first_removed = -1; //记录删除节点的首结点
    while (-1 != tmnod)
    { //遍历所有有效结点，同时判断是否有重复，有重复的执行删除操作
        if (isexist[abs(list[tmnod].key)])
        {
            if (0 == count)
            { //记录第一个删除节点，用于输出
                first_removed = tmnod;
            }
            else
            {
                list[pre_removed].next = tmnod;
            }
            list[pre].next = list[tmnod].next; //自右向左
            pre_removed = tmnod;
            list[pre_removed].next = -1;
            tmnod = list[pre].next;
            ++count;
        }
        else
        {
            list[pre].next = tmnod;
            isexist[abs(list[tmnod].key)] = true;
            pre = tmnod;
            tmnod = list[tmnod].next;
            list[pre].next = -1;
        }
    }
    int tmp = first;
    while (list[tmp].next != -1)
    {
        printf("%05d %d %05d\n", tmp, list[tmp].key, list[tmp].next);
        tmp = list[tmp].next;
    }
    printf("%05d %d -1\n", tmp, list[tmp]);
    tmp = first_removed;
    if (count != 0)
    { //有被删除的结点
        while (list[tmp].next != -1)
        {
            printf("%05d %d %05d\n", tmp, list[tmp].key, list[tmp].next);
            tmp = list[tmp].next;
        }
        printf("%05d %d -1\n", tmp, list[tmp]);
    }
    return 0;
}